package dp.test87;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/22 13:13
 */
public class Solution2 {
    // 递归解法
    public boolean isScramble(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        if (s1.equals("")) return true;
        int n = s1.length();
        if (n == 1) return s1.charAt(0) == s2.charAt(0);
        int[] temp = new int[26];
        for (int i = 0; i < n; i++) {
            temp[s1.charAt(i) - 'a']++;
            temp[s2.charAt(i) - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (temp[i] != 0) return false;
        }
        for (int l = 1; l < n; l++) {
            if ((isScramble(s1.substring(0, l), s2.substring(0, l)) && isScramble(s1.substring(l), s2.substring(l)))
                    || (isScramble(s1.substring(0, l), s2.substring(n - l)) && isScramble(s1.substring(l), s2.substring(0, n - l))))
                return true;
        }
        return false;
    }
}
